As a well-known NP-hard problem, the Three-Index Assignment Problem (AP3) hasattracted lots of research efforts for developing heuristics. However, existingheuristics either obtain less competitive solutions or consume too much time.In this paper, a new heuristic named Approximate Muscle guided Beam Search(AMBS) is developed to achieve a good trade-off between solution quality andrunning time. By combining the approximate muscle with beam search, thesolution space size can be significantly decreased, thus the time for searchingthe solution can be sharply reduced. Extensive experimental results on thebenchmark indicate that the new algorithm is able to obtain solutions withcompetitive quality and it can be employed on instances with largescale. Workof this paper not only proposes a new efficient heuristic, but also provides apromising method to improve the efficiency of beam search.
展开▼
